/**
 * 输入两颗二叉树,A,B,判断B是不是A的子结构.
 * 二叉树都是递归定义的,所以递归操作是比较常见的做法
 * B要是A的子结构,->B的根节点+左子树+右子树,都在A中存在且构成树形结构
 * 1.先确定起始位置
 * 2.再确定从该位置开始,后续的左右子树的内容是否一致
 */

public class suanfa15 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null) {
            return false;
        }
        //1.先找起始位置
        boolean result = false;
        if (root1.val == root2.val) {
            result = isSameChild(root1,root2);
        }
        if (result != true) {
            result = HasSubtree(root1.left,root2);
        }
        if (result != true) {
            result = HasSubtree(root1.right,root2);
        }
        return result;
    }

    //2.比较左右子树是否相等
    private boolean isSameChild(TreeNode begin, TreeNode begin_sub) {
        if (begin_sub == null) {
            return true;
        }
        if (begin == null) {
            return false;
        }
        if (begin.val != begin_sub.val) {
            return false;
        }
        //说明当前节点相等
        return isSameChild(begin.left,begin_sub.left) && isSameChild(begin.right,begin_sub.right);
    }
}
